package com.coder.algorithm.sort;

/**
 * 希尔排序
 *
 * @author yuhushuan
 * @date 2020/6/6 22:10
 */
public class ShellSort implements Sort {
    public ShellSort() {
        System.out.println("希尔排序");
    }

    @Override
    public void sort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        int len = array.length;
        int gap = len / 2;
        int temp;
        while (gap >= 1) {
            // 插入排序
            for (int i = gap; i < len; i++) {
                temp = array[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && array[preIndex] > temp) {
                    array[preIndex + gap] = array[preIndex];
                    preIndex -= gap;
                }
                array[preIndex + gap] = temp;
            }
            gap /= 2;
        }
    }

    private void sort2(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        int len = array.length;
        int gap = len / 2;
        int temp;
        while (gap >= 1) {
            // 分为 gap 个组
            for (int i = 0; i < gap; i++) {
                // 每个组为 i，i+1*gap，i+2*gap，……
                // 每个组作一个插入排序
                for (int j = i + gap; j < len; j += gap) {
                    temp = array[j];// 要插入的数
                    int k = j - gap;
                    while (k >= 0 && array[k] > temp) {
                        array[k + gap] = array[k];
                        k -= gap;
                    }
                    array[k + gap] = temp;
                }
            }
            gap /= 2;
        }
    }
}
